The present invention relates generally to forward error correction systems, and in particular to a product code based forward error correction system.
Digital electronic systems store and transmit copious amounts of information. Storage or transmission of digital information sometimes results, however, in corruption of some of the data. Defects in a storage media, or errors in the reading and writing of data from a storage media, may result in data errors. Similarly, transmission of data through a transmission channel may result in errors, through noise in the transmission channel or the inability of the transmitting or receiving unit to properly transmit or read data. As data storage and data transmission may be viewed as transmitting data to a media using a transmitting unit, and thereafter reading the data using a receiving unit, the remaining discussion will be in terms generally of data transmission.
Forward error correction (FEC) is often used to increase data reliability. Generally speaking, FEC systems encode data using an encoder at a transmitter and decode data using a decoder at the receiver. During encoding redundant information is added to the data. The redundant information allows determination by receiving units as to whether data corruption has occurred, and if so, the data that has been corrupted. Thus, the redundant information allows the data to be corrected within limits. The decoder generally decodes the data, generates an error polynomial, and uses the error polynomial to determine corrections to the data.
The encoded data is generally grouped in terms of code words. A code word is comprised of n symbols, of which k symbols are information symbols. The code word therefore contains nxe2x88x92k redundant symbols. The symbols are data words comprised of m bits. In a systematic encoding system, the nxe2x88x92k redundant symbols are appended to the information symbols, while in a non-systematic code the information symbols are also modified. For instance, for BCH codes, n=2mxe2x88x921 and k=nxe2x88x92mt. To correct t bits within the code word, mt bits of overhead/redundancy is needed. Each of the k and n symbols is made of 1 bit. For Reed-Solomon (RS) codes, n=2mxe2x88x921 and k=n2t. For RS codes, to correct t symbols within the code word, 2t symbols of redundancy is needed. Each of the k and n symbols comprise m bits.
In order to increase data transmission reliability increased numbers of redundant symbols are required. The use of additional redundant symbols, however, decreases the effective bandwidth of a transmission system or reduces the total amount of storage space available in a storage system. Moreover, the use of additional redundant symbols increases the amount of processing performed by both the transmitting unit and the receiving unit to create or interpret the redundant symbols.
Moreover, different coding schemes have different abilities to correct different types of errors. For example, errors may be randomly distributed in a data set, or the errors may be grouped together, i.e. be burst errors. Generally speaking, increasing the number of bits within a symbol increases the ability of an FEC system to correct burst errors. However, as indicated above, increasing the number of bits per symbol also increases encoding and decoding circuit size and power requirements since the code word becomes longer.
The present invention provides a multi-dimensional forward error correction system. In one embodiment the invention comprises an error correction system which decodes code words using a product code. In the product code symbols appear in multiple code words and each code is encoded using an error correction code having an error correction capability. In the embodiment the invention comprises a method of increasing error correction capability, the method comprising determining of plurality of code words which have a number of errors greater than the error correction capability of the error correction code used to encode the code word. The invention further comprises determining symbols common to at least two of the plurality of code words and inverting the common symbols.
In a further embodiment, the invention comprises a method of performing multi-dimensional forward error correction. The method comprises encoding using an error correction code information symbols comprised of input data to form first code words and second code words, the first and second code words sharing at least some symbols. The invention further comprises providing received symbols comprising potentially corrupted symbols of the first code words and second code words to a decoder, the received symbols forming first received symbols and second received symbols sharing at least some symbols. The invention further comprises decoding the first received symbols, including correcting at least some of the potentially corrupted symbols shared with the second received symbols and decoding the second received symbols, the second received symbols including symbols corrected during decoding of the first received symbols, including correcting at least some of the potentially corrupted symbols shared with the first received symbols. The invention further comprises further repetitively decoding the first received symbols and the second received symbols, each decoding using symbols as corrected during previous decoding. Further the invention comprises determining uncorrectable first received symbols and uncorrectable second received symbols in inverting symbols shared by at least one of the uncorrectable first received symbols and at least one of the uncorrectable second received symbols.
In a further embodiment, the present invention comprises a product code based decoding system. The decoding system comprises a memory storing received words and a plurality of decoders. The decoders are configured to receive first dimensioned code words and second dimensioned code words from a memory, and are configured to provide corrected first dimensioned code words and corrected second dimensioned code words to the memory. The decoding system further comprises a memory overwrite circuit, the memory overwrite circuit can figure to track uncorrectable first dimensioned code words and uncorrectable second dimensioned code words into invert symbols common to any one of the uncorrectable first dimensioned code words and any one of the uncorrectable second dimensioned code words.
These and other aspects of the present invention are more readily understood when considered in conjunction with the accompanying drawings and the following detailed description.